/*
 * @lc app=leetcode.cn id=221 lang=javascript
 *
 * [221] 最大正方形
 */

// @lc code=start
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    let res=0
    let less=0
    let help=function(i,j,n){
        let line=i+n
        let column=j+n
        if(line>=matrix.length||column>=matrix[0].length)return false
        for(;j<=column&&j<matrix[0].length;j++){
            if(matrix[line][j]==0){
                return false
            }
        }
        for(;i<=line&&i<matrix.length;i++){
            if(matrix[i][column]==0){
                return false
            }
        }
        return true
    }
    let dfs=function(i,j,n){
        if(!help(i,j,n))return
            res=Math.max(res,(n+1)*(n+1))
            dfs(i,j,n+1)
    }
    for(let i=0;i<matrix.length;i++){
        for(let j=0;j<matrix[0].length;j++){
            if(matrix[i][j]==1){
                less=1
                dfs(i,j,1)
            }
        }
    }
    return Math.max(res,less)
};
// @lc code=end

console.log(maximalSquare([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]))
var maximalSquare = function(matrix) {
    /* 
        思路一 DP 
        dp[i, j] 以坐标点i,j作为正方形右下角的最大正方形长度
        matrix[i, j] === '1' && i && j 
        dp[i, j] = Math.min(左， 上， 左上) + 1
        复杂度：时间 O(N*M) 空间 O(N*M) （新开二维辅助dp数组）
    */
    
    if (!matrix || !matrix.length) return 0

    const row = matrix.length, col = matrix[0].length, dp = []
    for (let i = 0; i < row; i++) dp.push(new Array(col).fill(0))

    let size = 0

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            // !i || !j 巧妙处理了 第一行于第一列的边界问题
            if (!i || !j || matrix[i][j] === '0') {
                dp[i][j] = matrix[i][j] - '0' // 利用减号 触发的隐式类型转换 巧妙的将远matrix[i][j] 中的string值转换为dp[i][j]中的Number 确保了dp中的类型一致
            } else {
                // 当前项作为正方形的右下点 还取决于 左、上、左上三处位置中的最小值
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
            }
            size = Math.max(size, dp[i][j])
        }
    }

    return size ** 2
}//dp